Behavior Trees

Two months ago, I was looking for a way to program an AI for a video game and I stumbled upon Behavior Trees. Today I’ll be talking about what they are, why they are used and how.

Originally, behavior trees were used in the game industry to model the behavior of NPC characters, it then started getting used in other domains, such as robotics.

Ultimately, it is a tree of predefined node types (root, control flow and execution) aimed to represent how “something” behaves. Each node returns either Success, Failure or Running.

Imagine you’re hungry and you’re trying to decide if you’re going to cook a meal or just order food. We can represent that with a behavior tree, like the following one:

It’s normal if you don’t understand what SELECTOR and SEQUENCE mean, but I’m sure you get the feeling of what this tree is trying to model.

Only one of the 2 actions can succeed, either you’ll cook a meal or order food.
You’ll only cook a meal if you’re motivated and have time.

Types of nodes

Action/Task/Leaf nodes

Leaf nodes can be split to two types:

Actions: Perform some kind of action, e.g. open a door.
Conditions: Check some kind of condition.

These nodes are typically user defined since they change depending on the usage/context.

Composite nodes

Composite nodes are nodes that contain one or more children and dictate how they are run and when to stop. The 3 most known and used ones are:

Sequence

Sequence nodes contain one or more children. Upon execution, it executes every child and fails when one of the children fails.

for child in children:
    status = child.run()
    if status == RUNNING or status == FAILURE:
        return status

return SUCCESS

In order for this node to be successful, all its children must succeed.

Selector

Selector nodes contain one or more children. Upon execution, it executes every child until one of them succeeds, otherwise it fails. You could look at it as the opposite of the sequence node.

for child in children:
    status = child.run()
    if status == RUNNING or status == SUCCESS:
        return status

return FAILURE

You can only do one of these actions.

Decorator

Decorator nodes can only have a single child. They are mostly used as utility nodes, for example:

Repeater: Runs the child node indefinitely or a number of times.
Inverter: Inverts the result of the child node.
AlwaysSucceed: Failure becomes Success.
UntilFail: Runs the child node until it fails.

Note: Decorators can have any kind of node as a child, it doesn’t need to be a leaf node.

Blackboard

In almost all scenarios, some nodes will want to “talk” to other nodes. Behavior Trees can have some kind of data store (blackboard, also called data context) that is global and accessible from all nodes to do so.

For example: Imagine you have a node that finds the closest enemy and another one that attacks it. The one that finds the enemy would put its coordinates in the blackboard and the one attacking it would retrieve the information and proceed.

This data store can be as simple as a dictionary of <string, object>.

Usage

Video games: To model the behaviors of enemies and non-player characters.
This is where behavior trees shine.
Conversational AI: I recently read a blog post about building a conversational AI using behavior trees and the result is quite impressive. How to Build an End-to-End Conversational AI System using Behavior Trees
Robotics Systems: These last years behavior trees have also received attention in the robotics domain. If you want to learn more, here’s an interesting paper: Behavior Trees in Robotics and AI: An Introduction.

Summary

Behavior Trees are an easy way to model and represent some kind of behavior. Each tree consists of composite nodes (sequences, selectors and decorators) and leaf/task nodes. They are very easy to make/create and super easy to visualize.

Behavior Trees are widely used in video game AIs but can also be used in other domains.
Happy coding!

Behavior Trees - Introduction